package leetcode3;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树专题
 */




class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Day6 {

    //1.相同的数
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if( (p==null && q!=null ) || (p!=null && q==null)) return false;
        if(p==null && q==null) return true;
        if(p.val != q.val) return false;
        if(!isSameTree(p.left,q.left)) return false;
        if(!isSameTree(p.right,q.right)) return false;
        return true;
    }

    //2.另一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //1.判断当前子树
        //2.判断左子树是否存在子树
        //3.判断右子树是否存在子树
        if(root == null) return false;
        if(isSameTree(root,subRoot)) return true;
        if(isSubtree(root.left,subRoot)) return true;
        if(isSubtree(root.right,subRoot)) return true;
        return false;
    }

    //3.翻转二叉树
    Stack<TreeNode> stack = new Stack<>();
    public TreeNode invertTree(TreeNode root) {
        //1.翻转左右子树
        //2.递归翻转左右子树
        if(root == null) return root;
        stack.push(root.left);
        stack.push(root.right);
        root.left = stack.pop();
        root.right = stack.pop();
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //4.平衡二叉树
    public boolean isBalanced(TreeNode root) {
        //1.判断当前树的左右高度是否>1
        //2.递归左右子树
        if(root == null ) return true;
        return treeDeep(root)>=0;
    }
    //求树的高度,并判断左右树是否符合平衡树
    public int treeDeep(TreeNode root) {
        if(root == null) return 0;
        int leftH = treeDeep(root.left);
        int rightH = treeDeep(root.right);
        int tmp = Math.abs(leftH-rightH);
        if(leftH >=0 && rightH >=0 && tmp < 2) {
            return 1 + Math.max(leftH,rightH);
        }else {
            //不符合
            return -1;
        }
    }

    //5.对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return symmetric(root.left,root.right);
    }
    //判断两棵子树是否对称相等
    public boolean symmetric(TreeNode leftR,TreeNode rightR) {
        if(leftR == null && rightR == null) return true;
        if(leftR==null && rightR!=null || leftR!=null && rightR==null) return false;
        if(leftR.val != rightR.val) return false;
        //判断对称子树
        if(symmetric(leftR.left,rightR.right) && symmetric(leftR.right,rightR.left)) return true;
        return false;
    }






}
